package com.algorithm;

public class MergeSort {

    public static void main(String[] args) {


        int[] os = {3, 4, 2, 1, -3, 2, 8, 3, 29, 3, 2, 1, 99, 30};
        for (int i : mergeSort(os)) {
            System.out.print(i + ",");
        }
        System.out.print("\b");

    }


    public static int[] mergeSort(int[] os) {
        int[] tmp = new int[os.length];
        dfs(os, 0, os.length - 1, tmp);
        return os;
    }

    public static void dfs(int[] os, int start, int end, int[] tmp) {
        if (start >= end) {
            return;
        }

        int mid = start + ((end - start) >>> 1);

        dfs(os, start, mid, tmp);
        dfs(os, mid + 1, end, tmp);

        int s = start, m = mid + 1;

        for (int i = start; i <= end; i++) {
            if (s > mid) {
                tmp[i] = os[m];
                m++;
                continue;
            }
            if (m > end) {
                tmp[i] = os[s];
                s++;
                continue;
            }

            if (os[s] < os[m]) {
                tmp[i] = os[s];
                s++;
            } else {
                tmp[i] = os[m];
                m++;
            }

        }

        while (start <= end) {
            os[start] = tmp[start];
            start++;
        }


    }


}


